//
// Created by hay boy on 2022/7/8.
//

#ifndef ALGORITHMS_SORTEDCHAIN_H
#define ALGORITHMS_SORTEDCHAIN_H
#include <iostream>
#include "dictionary.h"
#include "PairNode.h"
using namespace std;
template<class K,class E>
class SortedChain:public Dictionary<K,E>{
protected:
    pairNode<K,E>* firstNode;
    int dSize;
public:
    SortedChain(){
        firstNode = nullptr;
        dSize = 0;
    }
    ~SortedChain();
    bool empty() const{
        return dSize==0;
    }
    int size() const{
        return dSize;
    }
    void clear();
    pair<const K,E>* find(const K&) const;
    void erase(const K&);
    void insert(const pair<const K,E>&);
    void output(ostream& out) const;
    template<class T,class Y>
    friend ostream& operator<<(ostream& out,const SortedChain<T,Y>& x);
};

template<class K, class E>
SortedChain<K, E>::~SortedChain() {
    while(firstNode!= nullptr){
        pairNode<K,E>* nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

template<class K, class E>
pair<const K, E>* SortedChain<K, E>::find(const K &theKey) const {
    pairNode<K,E>* currentNode = firstNode;
    while(currentNode!= nullptr&&currentNode->element.first!=theKey){
        currentNode = currentNode->next;
    }
    if(currentNode!=nullptr&&currentNode->element.first==theKey){
        return &currentNode->element;
    }
    return nullptr;
//    return new pair<const K,E>(theKey,E());
}

template<class K, class E>
void SortedChain<K, E>::erase(const K &theKey) {
    pairNode<K,E> *p = firstNode;
    pairNode<K,E> *tp = nullptr;
    while(p!= nullptr&&p->element.first<theKey){
        tp = p;
        p = p->next;
    }
    if(p!= nullptr&&p->element.first==theKey){
        if(tp== nullptr){
            firstNode = p->next;
        }else{
            tp->next = p->next;
        }
        delete p;
        dSize--;
    }
}

template<class K, class E>
void SortedChain<K, E>::insert(const pair<const K, E> &thePair) {
    pairNode<K,E>*p = firstNode,*tp = nullptr;
    while(p!= nullptr&&p->element.first<thePair.first){
        tp = p;
        p = p->next;
    }
    if(p!= nullptr&&p->element.first==thePair.first){
        p->element.second = thePair.second;
        return;
    }
    pairNode<K,E>* newNode = new pairNode<K,E>(thePair,p);
    if(tp== nullptr){
        firstNode = newNode;
    }else{
        tp->next = newNode;
    }
    dSize++;
}

template<class K, class E>
void SortedChain<K, E>::output(ostream &out) const {
    for(pairNode<K,E>* currentNode=firstNode;currentNode!= nullptr;currentNode=currentNode=currentNode->next){
        out<<currentNode->element.first<<" "<<currentNode->element.second<<" ";
    }

}
template<class K,class E>
ostream& operator<<(ostream& out,const SortedChain<K,E>& x){
    x.output(out);
    return out;
}

template<class K, class E>
void SortedChain<K, E>::clear() {
    while(firstNode!= nullptr){
        pairNode<K,E>* nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
    dSize = 0;
}

#endif //ALGORITHMS_SORTEDCHAIN_H
